// 剩余系 欧拉定理 扩展欧拉定理
// 测试链接 ：https://www.luogu.com.cn/problem/P5091
// 相关帖子 ：https://www.cnblogs.com/dx123/p/16723239.html
// 相关帖子 ：https://oi-wiki.org/math/number-theory/fermat/
// 提交以下的code，可以直接通过

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int MAXN = 20000001;
int a, b, m, phi, flag;
char s[MAXN];

// 试除法求欧拉函数
int get_phi(int n)
{
    int ans = n;
    for(int i = 2; i <= n / i; ++i)
    {
        if(n % i == 0)
        {
            ans = ans / i * (i - 1);
            while(n % i == 0) n /= i;
        }
    }
    if(n > 1) ans = ans / n * (n - 1);
    return ans;
}

// 降幂操作
int lowerPow(int phi)
{
    int b = 0;
    for(int i = 0; s[i]; ++i)
    {
        b = b * 10 + s[i] - '0';
        if(b >= phi)
        {
            flag = 1;
            b %= phi;
        }
    }
    if(flag) b += phi;
    return b;
}

// 快速幂
int quickPow(ll a, int b)
{
    int ans = 1;
    while(b)
    {
        if(b & 1) ans = ans * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return ans;
}

int main()
{
    scanf("%d%d%s", &a, &m, s);
    phi = get_phi(m);
    b = lowerPow(phi); // 降幂
    printf("%d\n", quickPow(a, b));

    return 0;
}